Leetcode 891. Sum of Subsequence Widths - Week15

题目链接

Leetcode 891. Sum of Subsequence Widths

题目内容

Given an array of integers A, consider all non-empty subsequences of A.

For any sequence S, let the width of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large, return the answer modulo 10^9 + 7.

Example

Input: [2,1,3]

Output: 6

Explanation:

Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]. The corresponding widths are 0, 0, 0, 1, 1, 2, 2. The sum of these widths is 6.

解题思路

题目意思就是求其给出数组的所有子序列的宽度和，而这个序列的宽度和为该序列最大值减去该序列最小值。

这里很容易想的的方法就是暴力穷举，但是显然这种这么容易想到的方法不会得到AC，那么我们仔细分析一下这个题目，既然对于每个序列我们只需要知道每个序列的最大值和最小值，那么我们可以通过先对我们数组进行一个排序操作，然后我们的解就可以通过一次遍历计算得到，对于每个a[i]有2^i个子序列以他为最大值，有2^(n-i-1)个字序列以它为最小值，对应每个i

$$Ans = Ans + a[i](2^i) - a[i]2^{n - i - 1}$$

ANS的对应公式如下

$$Ans = \sum_{i=1}^{n}(2^{n-i-1} - 2^{i}) * ai$$

进行优化后，我们字序列数(num)无需每次重新计算，我们每次加上A[i] * num 并减去 A[A.size() - i - 1] * num，进行遍历即可

经过有效分析，题目就较为简单了，在上面的基础上，我们再加上一个取余操作就可以得出了

在不去掉C++的输入输出的兼容性的情况下，提交detail为

题目代码

class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        long width = 0, num = 1;
        long mod = 1e9 + 7;

        for (int i = 0; i < A.size(); i++) {
            width = ((width + A[i] * num) - (A[A.size() - i - 1] * num)) % mod;
            num = (num << 1) % mod;
        }

        return width % mod;
    }
};